// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 *
 * @author: yanking
 * Create time: 2022-03-13 22:31
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetCodeT.DynamicPlan;

import java.util.Stack;

public class IsValid {
    /**
     * 判断括号是否匹配
     */
    public boolean isValid(String s) {
        // 使用栈 -> 匹配出栈
        int n = s.length();
        if (n == 0) {
            return false;
        }
        Stack<Character> stack = new Stack<>();
        if (s.charAt(0) == '}' || s.charAt(0) == ']' || s.charAt(0) == ')') {
            // 开头第一个元素发生不匹配
            return false;
        }
        stack.push(s.charAt(0));
        int k = 1;
        while (k < s.length()) {
            char c = s.charAt(k);
            if (c == '(' || c == '{' || c == '[') {
                stack.push(c);
                ++k;
                continue;
            }
            if (c == ')') {
                if (stack.isEmpty()) {return false;}
                Character top = stack.pop();
                if (top != '(') {
                    // 发生符号不匹配
                    return false;
                }
            }
            if (c == ']') {
                if (stack.isEmpty()) {return false;}
                Character top = stack.pop();
                if (top != '[') {
                    // 发生符号不匹配
                    return false;
                }
            }
            if (c == '}') {
                if (stack.isEmpty()) {return false;}
                Character top = stack.pop();
                if (top != '{') {
                    // 发生符号不匹配
                    return false;
                }
            }
            ++k;
        }

        return stack.isEmpty();
    }
}
